# 383. 赎金信
# 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
# 如果可以，返回 true ；否则返回 false 。
# magazine 中的每个字符只能在 ransomNote 中使用一次。

# 空间复杂度：O(m+n)，m为ransomNote的长度，n为magazine的长度，都需要遍历一次。
# 时间复杂度：O(|S|)，S 是字符集，这道题中 SSS 为全部小写英语字母，因此∣S∣=26。
def canConstruct(ransomNote: str, magazine: str) -> bool:
    char_dict = {}
    for char_ in magazine:
        char_count = char_dict.get(char_, 0)
        char_count += 1
        char_dict[char_] = char_count
    re = True
    index = 0
    while re and index < len(ransomNote):
        ransom_char = ransomNote[index]
        char_count = char_dict.get(ransom_char, 0)
        if char_count > 0:
            char_count -= 1
            char_dict[ransom_char] = char_count
            index += 1
        else:
            re = False

    return re


result = canConstruct("abcdef", "aabcdeee")
print(f"result:{result}")
